/*
   @Copyright:LintCode
   @Author:   tjyemail
   @Problem:  http://www.lintcode.com/problem/permutation-sequence
   @Language: C++
   @Datetime: 16-02-09 08:20
   */

class Solution {
public:
	/**
	 * @param n: n
	 * @param k: the kth permutation
	 * @return: return the k-th permutation
	 * Tip: Using STL next_permutation
	 * See problem 52 next permutation for more
	 */
	string getPermutation(int n, int k) {
		string s(n,'0');
		for(; n--; s[n]='1'+n);	// build string in ascending order
		for(; --k; next_permutation(s.begin(),s.end()));
		return s;
	}
};
